package com.wtgroup.demo.牛客;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

/**
 * @author nisus
 * @version 0.1
 * @since 2023/6/6 13:11
 */
public class HJ68_成绩排序 {

    static class D {
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            // 注意 hasNext 和 hasNextLine 的区别
            int i = 0;
            int cnt = 0;
            int sortDirect = 0;
            User[] users = null;
            int j = -1;
            while (in.hasNextLine() && j < cnt) { // 注意 while 处理多个 case
                i++;
                String line = in.nextLine();
                if (i == 1) {
                    cnt = Integer.parseInt(line.trim());
                    users = new User[cnt];
                    continue;
                }
                if (i == 2) {
                    sortDirect = Integer.parseInt(line.trim());
                    continue;
                }

                line = line.trim();
                String[] split = line.split(" ");
                User u = new User(split[0], Integer.parseInt(split[1]));
                users[++j] = u;
            }

            //sort(users, sortDirect, 0, users.length - 1); // 手撕的快排不是稳定的
            Arrays.sort(users, new Comparator<User>() {
                @Override
                public int compare(User o1, User o2) {
                    return 0;
                }
            });

            for (User u : users) {
                System.out.println(u.name + " " + u.score);
            }

        }

        static void sort(User[] users, int direct, int L, int R) {
            if (L >= R) return;


            int[] p = partition(users, direct, L, R);
            sort(users, direct, L, p[0] - 1);
            sort(users, direct, p[1] + 1, R);

        }

        static int[] partition(User[] users, int direct, int L, int R) {
            User pivot = users[R];
            int i = L, l = L, r = R;
            for (; i <= r;) {
                User curr = users[i];
                int diff = curr.score - pivot.score;
                diff = direct == 0 ? -diff : diff;
                if (diff > 0) {
                    swap(users, i, r);
                    r--;
                } else if (diff < 0) {
                    swap(users, i, l);
                    l++;
                    i++;
                } else {
                    i++;
                }
            }

            return new int[] {l, r};
        }

        static void swap(User[] users, int i, int j) {
            User tmp = users[i];
            users[i] = users[j];
            users[j] = tmp;
        }


        static class User {
            String name;
            int score;
            public User() {
            }
            public User(String name, int score) {
                this.name = name;
                this.score = score;
            }
        }
    }
}
